/*
 * @lc app=leetcode.cn id=60 lang=cpp
 *
 * [60] 排列序列
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    string getPermutation(int n, int k)
    {
        vector<int> factorial(n);
        factorial[0] = 1;
        for (int i = 1; i < n; ++i)
        {
            factorial[i] = factorial[i - 1] * i;
        }

        vector<int> nums(n, 0);
        iota(begin(nums), end(nums), 1);
        string res;
        --k;
        for(int i = n - 1; i != -1; --i)
        {
            auto it = nums.begin() + k / factorial[i];
            res += '0' + *it;
            nums.erase(it);
            k %= factorial[i];
        }
        return res;
    }
};

// int main()
// {
//     Solution().getPermutation(3, 3);
//     return 0;
// }
// @lc code=end
